import java.util.*;

public class O07 {
    public static void main(String[] args) {
        O07 o = new O07();
        System.out.println(o.buildTree(new int[]{1,2},new int[]{2,1}));
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length==0)
            return null;
        if (preorder.length==1)
            return new TreeNode(preorder[0]);
        TreeNode root = new TreeNode(preorder[0]);
        List<Integer> p = new ArrayList<>();
        List<Integer> i = new ArrayList<>();
        for (int i1 : preorder) {
            p.add(i1);
        }
        for (int i1 : inorder) {
            i.add(i1);
        }
        int sub = searchI(preorder[0],i);
        return getTreeNode(root, p, i, sub);
    }

    private TreeNode getTreeNode(TreeNode root, List<Integer> p, List<Integer> i, int sub) {
        int psub = searchP(i.subList(0,sub),p);
        if (psub==-1){
            root.left = backStack(p.subList(1,p.size()),i.subList(0,sub));
        }else {
            root.left = backStack(p.subList(1,psub),i.subList(0,sub));
            root.right = backStack(p.subList(psub,p.size()),i.subList(sub+1,i.size()));
        }
        return root;
    }

    TreeNode backStack(List<Integer> preorder, List<Integer> inorder){
        if (preorder.size()==0||inorder.size()==0)
            return null;
        TreeNode treeNode = new TreeNode(preorder.get(0));
        int sub = searchI(preorder.get(0),inorder);
        return getTreeNode(treeNode, preorder, inorder, sub);
    }
    int searchI(int target, List<Integer> nums){
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i)==target)
                return i;
        }
        return -1;
    }
    int searchP(List<Integer> target, List<Integer> nums){
        Set<Integer> set = new HashSet<>(target);
        for (int i = 1; i < nums.size(); i++) {
            if (!set.contains(nums.get(i)))
                return i;
        }
        return -1;
    }
}
